Get The Intersection Of Two Arrays

Here's a quick exercise: If there are two unsorted arrays, write a function that returns their intersection.

做個動腦練習，假設有兩個 unsorted arrays，寫一個 function 回傳兩 array 交集的值
先不要偷看答案唷～

提示：使用linear search

Answer:

const arrayA = [1,6,3,9,17,22,18,7,5,2,21,12,37,33,8,109,77,23,14,11];
const arrayB = [2,5,8,12,75,17,23,14,36,33,7,17,9,77,56,62,1,102,3];

finction getIntersection(arrA,arrB){
    const result=[];
    for(let i =0; i<arrA.length;i++){
        for(let j=0;j<arrB.length;j++){
            if(arrA[i]===arrB[j]){
                result.push(arrA[i]);
            }
        }
    }
    return result;
}

getIntersection(arrayA ,arrayB ); // [1, 3, 9, 17, 17, 7, 5, 2, 12, 33, 8, 77, 23, 14]

Here's a quick exercise: If there are two sorted arrays, write a function that returns their intersection.

做個動腦練習，假設有兩個 sorted arrays，寫一個 function 回傳兩 array 交集的值
先不要偷看答案唷～

提示：使用binary search

Answer:

 const arrayA = [1, 2, 3, 5, 6, 7, 8, 9, 11, 12, 14, 17, 18, 21, 22, 23, 33, 37, 77, 109];
 const arrayB = [1, 2, 3, 5, 7, 8, 9, 12, 14, 17, 23, 33, 36, 56, 62, 75, 77, 102];

function binartSearch(arr, target) {
    let min = 0,
        max = arr.length - 1;
        while (min <= max) {
            let mid = Math.floor((min + max) / 2);
            if (arr[mid] === target) {
                return true;
            } else if (arr[mid] < target) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
    return false;
}

function getIntersectionBinary(arrA, arrB) {
    let intersection = [];
    for (let i = 0; i < arrA.length; i++) {
        if (binartSearch(arrB, arrA[i])) {
            intersection.push(arrA[i]);
         }
    }
    return intersection;
}

console.log(getIntersectionBinary(arrayA, arrayB)); // [1, 2, 3, 5, 7, 8, 9, 12, 14, 17, 23, 33, 77]